using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0337. 打家劫舍 III")]
    public class No0337_Rob : AbsBaseTestItem
    {
        /*
        在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

        计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(Rob, new TreeNode(3)
            {
                left = new TreeNode(2)
                {
                    left = new TreeNode(3),
                },
                right = new TreeNode(3)
                {
                    right = new TreeNode(1),
                },
            }, 7);
            Assert.TestExe(Rob, new TreeNode(3)
            {
                left = new TreeNode(4)
                {
                    left = new TreeNode(1),
                    right = new TreeNode(3),
                },
                right = new TreeNode(5)
                {
                    right = new TreeNode(1),
                },
            }, 9);
        }

        public int Rob(TreeNode root)
        {
            int[] dfs(TreeNode node)
            {
                if (node == null)
                {
                    return new int[] { 0, 0 };
                }
                int[] l = dfs(node.left);
                int[] r = dfs(node.right);
                int selected = node.val + l[1] + r[1];
                int notSelected = Math.Max(l[0], l[1]) + Math.Max(r[0], r[1]);
                return new int[] { selected, notSelected };
            }
            int[] rootStatus = dfs(root);
            return Math.Max(rootStatus[0], rootStatus[1]);
        }
    }
}
